package SortMethod;

import java.util.Arrays;

//通过归并排序来解决一些问题，比如算数组中的逆序数
public class NiXuByMerge {

    private NiXuByMerge (){}

    public static <E extends Comparable<E>> void sort(E[] arr){
        int n = sort(arr,0,arr.length-1);
        System.out.println(n);
    }

    private static <E extends Comparable<E>> int sort(E[] arr,int l,int r){
        if (l >= r)
            return 0;
        int res = 0;
        int mid = l + (r-l)/2;
        res += sort(arr,l,mid);
        res += sort(arr,mid+1,r);
        if (arr[mid].compareTo(arr[mid + 1]) > 0)
            res += merge(arr,l,mid,r);
        return res;
    }

    //合并两个有序的数组 arr[l,mid] arr[mid+1,r]
    private static <E extends Comparable<E>> int merge(E[] arr,int l,int mid,int r){
        E[] temp = Arrays.copyOfRange(arr,l,r+1);
        int i = l,j = mid+1,res = 0;
        for (int k = l; k <= r; k++) {
            if (i > mid){
                arr[k] = temp[j - l];j++;
            } else if (j > r){
                arr[k] = temp[i - l];i++;
            } else if (temp[i - l].compareTo(temp[j - l])<0){
                arr[k] = temp[i - l];i++;
            } else {
                res += mid - i + 1;
                arr[k] = temp[j - l];j++;
            }
        }
        return res;
    }

}
